class node():
    def __init__(self,key=None):
        self.key=key
        self.p=None
        self.degree=0
        self.child=None
        self.sibling=None
    def __str__(self):
        return str(self.key)
    def __repr__(self):
        return str(self)
class binomial_heap():
    def __init__(self):
        self.head=None
        self.dict={} #assume all elements are different
    def minimum(self):
        y=None
        x=self.head
        minimum=None
        while x is not None:
            if minimum is None or x.key<minimum:
                minimum=x.key
            y=x
            x=x.sibling
        return minimum
    def link(self,y,z): #node y and node z
        y.p=z
        y.sibling=z.child
        z.child=y
        z.degree+=1
    def merge(self,other):
        h1_prev=None
        h1=self.head
        h2=other.head
        while h2 is not None and h1 is not None:
            if h2.degree<h1.degree:
                tmp=h2.sibling
                h2.sibling=h1
                if h1_prev is None:
                    self.head=h2
                else:
                    h1_prev.sibling=h2
                h2=tmp
            else:
                h1_prev=h1
                h1=h1.sibling
        if h2 is not None:
            if h1_prev is not None:
                h1_prev.sibling=h2
            else:
                self.head=h2 #not h1
    def union(self,other):
        self.merge(other)
        self.dict.update(other.dict) #extend the dict
        del other
        if self.head is None:
            return
        prev_x=None
        x=self.head
        next_x=x.sibling
        while next_x is not None:
            if x.degree<next_x.degree or \
               next_x.sibling is not None and x.degree==next_x.sibling.degree:
                prev_x=x
                x=next_x
                next_x=x.sibling
            else:
                if x.key<=next_x.key:
                    x.sibling=next_x.sibling
                    self.link(next_x,x)
                    next_x=x.sibling
                else:
                    if prev_x is None:
                        self.head=next_x
                    else:
                        prev_x.sibling=next_x
                    self.link(x,next_x)
                    x=next_x
                    next_x=x.sibling #prev_x not change
    def insert(self,k):
        H2=binomial_heap()
        x=node(key=k)
        H2.head=x
        H2.dict[k]=x
        self.union(H2)
    def minimum_x(self): #return the node and its prev
        if self.head is None:
            return None,None
        y=None
        x=self.head
        minimum=None
        min_prev=None
        while x is not None:
            if minimum is None or x.key<minimum.key:
                minimum=x
                min_prev=y
            y=x
            x=x.sibling
        return min_prev,minimum        
    def extract_min(self):
        x_prev,x=self.minimum_x()
        if x is None:
            raise Exception('extract from empty heap')
        if x==self.head:
            self.head=x.sibling
        else: #if x_prev is not None:
            x_prev.sibling=x.sibling
        u=x.child
        u_prev=None
        while u is not None:
            u.p=None
            tmp=u.sibling
            u.sibling=u_prev
            u_prev=u
            u=tmp
        H2=binomial_heap()
        H2.head=u_prev #H2.dict is not correct now
        self.union(H2)
        del self.dict[x.key]
        return x.key
    def decrease_key(self,k,knew):
        if knew>k:
            raise Exception('new key is not smaller than current key')
        x=self.dict[k]
        self.dict[knew]=x
        del self.dict[k]
        x.key=knew
        y=x.p
        while y is not None and x.key<y.key:
            y.key,x.key=x.key,y.key
            self.dict[x.key],self.dict[y.key]=self.dict[y.key],self.dict[x.key]
            x=y
            y=x.p
    def delete(self,k):
        self.decrease_key(k,-1) #assume all keys are positive
        self.extract_min()

    def print_heap(self):
        h=self.head
        while h is not None:
            print '  head:', h,
            if h.child is not None:
                print 'child:',
                stk=[]
                stk.append(h.child)
                while len(stk)>0:
                    u=stk.pop()
                    print u,
                    if u.sibling is not None:
                        stk.append(u.sibling)
                    if u.child is not None:
                        stk.append(u.child)
            print
            h=h.sibling

if __name__=='__main__':
    a=binomial_heap()
    for i in range(10):
        a.insert(i+1)
    a.print_heap()
    print 'min is', a.minimum()
    print 'extract min:', a.extract_min()
    a.print_heap()
    a.decrease_key(6,0)
    print 'decrease key 6 to 0:'
    a.print_heap()
    a.delete(7)
    print 'delete 7:'
    a.print_heap()


